/**
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 * 二叉树的最近公共组先
 * @param root 树根
 * @param p 节点1
 * @param q 节点2
 */
export const lowestCommonAncestor = (root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null => {
    // 根为空
    if (root === null) return null

    // 两个节点有一个和根节点相同, 那么返回其本身
    if (root === p) return p
    if (root === q) return q

    // 根节点均大于p和q, 往右边找
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.right, p, q)
    }

    // 根节点均小于p和q, 往左边找
    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.left, p, q)
    }
    // 根节点在p和q之间, 说明根节点就是他们的最近公共组先
    return root;
};


// 适用任何的二叉树
const lowestCommonAncestor2 = (root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null => {
    // 根为空
    if (root === null) return null

    // 两个节点有一个和根节点相同, 那么返回其本身
    if (root === p) return p
    if (root === q) return q

    // 查找以root.left为根的p和q的最近公共组先
    const left = lowestCommonAncestor2(root.left, p, q);

    // 查找以root.right为根的p和q的最近公共组先
    const right = lowestCommonAncestor2(root.right, p, q)

    // 左边并且右边不为空
    if (left !== null && right !== null) return root;

    // 那边不为空, 就返回那边
    return left !== null ? left : right
};